package Queue_and_Stack;

/*
打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
每个拨轮可以自由旋转：例如把 '9' 变为'0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/kj48j/
 */

import java.util.*;

public class _22打开转盘锁 {
    public static void main(String[] args) {

    }

    //官解  BFS
    //具体地，我们在一开始将 (0000,0) 加入队列，并使用该队列进行广度优先搜索。
    //在搜索的过程中，设当前搜索到的数字为 status，旋转的次数为 step，我们可以枚举 status 通过一次旋转得到的数字。
    //设其中的某个数字为 next_status，如果其没有被搜索过，我们就将 (next_status,step+1) 加入队列。如果搜索到了 target，我们就返回其对应的旋转次数。
    //为了避免搜索到死亡数字，我们可以使用哈希表存储 deadends 中的所有元素，这样在搜索的过程中，我们可以均摊 O(1) 地判断一个数字是否为死亡数字。
    //同时，我们还需要一个哈希表存储所有搜索到的状态，避免重复搜索。
    //如果搜索完成后，我们仍没有搜索到 target，说明我们无法解锁，返回 −1。

    //难点在于编写每一步至多增加 由4个波轮的数字变化导致的8个数字的代码
    //BFS是一个算法，它是一个框架，解决每一步搜索的代码问题，就可以使用BFS思路
    class Solution {
        public int openLock(String[] deadends, String target) {
            if ("0000".equals(target)) {
                return 0;
            }

            Set<String> dead = new HashSet<String>();
            for (String deadend : deadends) {
                dead.add(deadend);
            }
            if (dead.contains("0000")) {
                return -1;
            }

            int step = 0;
            Queue<String> queue = new LinkedList<String>();
            queue.offer("0000");
            Set<String> seen = new HashSet<String>();
            seen.add("0000");

            while (!queue.isEmpty()) {
                ++step;
                int size = queue.size();
                for (int i = 0; i < size; ++i) {
                    String status = queue.poll();
                    for (String nextStatus : get(status)) {
                        if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
                            if (nextStatus.equals(target)) {
                                return step;
                            }
                            queue.offer(nextStatus);
                            seen.add(nextStatus);
                        }
                    }
                }
            }

            return -1;
        }

        public char numPrev(char x) {
            return x == '0' ? '9' : (char) (x - 1);
        }

        public char numSucc(char x) {
            return x == '9' ? '0' : (char) (x + 1);
        }

        // 枚举 status 通过一次旋转得到的数字
        public List<String> get(String status) {
            List<String> ret = new ArrayList<String>();
            char[] array = status.toCharArray();
            for (int i = 0; i < 4; ++i) {
                char num = array[i];
                array[i] = numPrev(num);
                ret.add(new String(array));
                array[i] = numSucc(num);
                ret.add(new String(array));
                array[i] = num;
            }
            return ret;
        }
    }

    //BFS
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }

        HashSet<String> dead = new HashSet<>();
        Collections.addAll(dead, deadends);
        if (dead.contains("0000")) {
            return -1;
        }

        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        HashSet<String> seen = new HashSet<>();
        seen.add("0000");

        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String status = queue.poll();
                for (String nextstatu : get(status)) {
                    if(!seen.contains(nextstatu) && !dead.contains(nextstatu)) {
                        if (nextstatu.equals(target)) {
                            return step;
                        }
                        queue.offer(nextstatu);
                        seen.add(nextstatu);
                    }
                }
            }
        }
        return -1;
    }
    public char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }
    public char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }
    public List<String> get(String status) {
        List<String> nextNum = new ArrayList<>();
        char[] charArray = status.toCharArray();
        for (int i = 0; i < 4; i++) {
            char num = charArray[i];
            charArray[i] = numPrev(num);
            nextNum.add(new String(charArray));
            charArray[i] = numSucc(num);
            nextNum.add(new String(charArray));
            charArray[i] = num;
        }
        return nextNum;
    }


    //双向BFS
    //「双向 BFS」的基本实现思路如下：
    //创建「两个队列」分别用于两个方向的搜索；
    //创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
    //为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
    //如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
    //作者：宫水三叶
    //链接：https://leetcode.cn/problems/open-the-lock/solutions/843986/gong-shui-san-xie-yi-ti-shuang-jie-shuan-wyr9/
    class Solution2 {
        String t, s;
        Set<String> set = new HashSet<>();
        public int openLock(String[] _ds, String _t) {
            s = "0000";
            t = _t;
            if (s.equals(t)) return 0;
            for (String d : _ds) set.add(d);
            if (set.contains(s)) return -1;
            int ans = bfs();
            return ans;
        }
        int bfs() {
            // d1 代表从起点 s 开始搜索（正向）
            // d2 代表从结尾 t 开始搜索（反向）
            Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
            /*
             * m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来
             * e.g.
             * m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋转 1 次而来
             * m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋转 3 次而来
             */
            Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
            d1.addLast(s);
            m1.put(s, 0);
            d2.addLast(t);
            m2.put(t, 0);

            /*
             * 只有两个队列都不空，才有必要继续往下搜索
             * 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
             * e.g.
             * 例如，如果 d1 为空了，说明从 s 搜索到底都搜索不到 t，反向搜索也没必要进行了
             */
            while (!d1.isEmpty() && !d2.isEmpty()) {
                int t = -1;
                if (d1.size() <= d2.size()) {
                    t = update(d1, m1, m2);
                } else {
                    t = update(d2, m2, m1);
                }
                if (t != -1) return t;
            }
            return -1;
        }
        int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
            int m = deque.size();
            while (m-- > 0) {
                String poll = deque.pollFirst();
                char[] pcs = poll.toCharArray();
                int step = cur.get(poll);
                // 枚举替换哪个字符
                for (int i = 0; i < 4; i++) {
                    // 能「正向转」也能「反向转」，这里直接枚举偏移量 [-1,1] 然后跳过 0
                    for (int j = -1; j <= 1; j++) {
                        if (j == 0) continue;

                        // 求得替换字符串 str
                        int origin = pcs[i] - '0';
                        int next = (origin + j) % 10;
                        if (next == -1) next = 9;

                        char[] clone = pcs.clone();
                        clone[i] = (char)(next + '0');
                        String str = String.valueOf(clone);

                        if (set.contains(str)) continue;
                        if (cur.containsKey(str)) continue;

                        // 如果在「另一方向」找到过，说明找到了最短路，否则加入队列
                        if (other.containsKey(str)) {
                            return step + 1 + other.get(str);
                        } else {
                            deque.addLast(str);
                            cur.put(str, step + 1);
                        }
                    }
                }
            }
            return -1;
        }
    }


}
